package com.fun.tasks;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FindMaxSubarray {

	public static void main(String[] args) {
		int[] array = new int[] { 5, 2, -1 };

		Result result = getMaxSubarray(array);

		System.out.println("Total: " + result.totalSum);
		System.out.println("Sub array: " + Arrays.toString(result.subArray));
	}

	public static Result getMaxSubarray(int[] array) {
		if (array.length == 0) {
			return new Result(0, new int[] {});
		}

		if (array.length == 1) {
			return new Result(array[0], new int[] { array[0] });
		}

		HashMap<Integer, Result> store = new HashMap<Integer, Result>();

		Result result = getMaxSubarray(store, array, array.length - 1);

		// lets use dynamic programming for this task
		return result;
	}

	private static Result getMaxSubarray(Map<Integer, Result> store,
			int[] array, int i) {
		if (i <= 0) {
			return new Result(array[0], new int[] { array[0] });
		}

		final Result prevResult;
		Integer key = i - 1;

		if (store.containsKey(key)) {
			prevResult = store.get(key);
		} else {
			prevResult = getMaxSubarray(store, array, i - 1);
			store.put(key, prevResult);
		}

		if (prevResult.totalSum > prevResult.totalSum + array[i]) {
			return prevResult;
		} else {
			int[] subArray = new int[prevResult.subArray.length + 1];

			subArray[subArray.length - 1] = array[i];

			System.arraycopy(prevResult.subArray, 0, subArray, 0,
					prevResult.subArray.length);

			return new Result(prevResult.totalSum + array[i], subArray);
		}
	}

	private static class Result {
		int totalSum = 0;
		int[] subArray;

		public Result(int totalSum, int[] subArray) {
			this.totalSum = totalSum;
			this.subArray = subArray;
		}

	}

}
